<?php
class TreeNode {
    public $val = null;
    public $left = null;
    public $right = null;
    function __construct($value) {
        $this->val = $value;
    }
}

class Solution {

    /**
     * @param TreeNode $root
     * @return Integer
     */
    function minDepth($root) {
        if ($root == null) {
            return 0;
        }
        if ($root->left == null && $root->right == null) {
            return 1;
        }
        $min_depth = PHP_INT_MAX;
        if ($root->left) {
            $min_depth = min($this->minDepth($root->left), $min_depth);
        }
        if ($root->right) {
            $min_depth = min($this->minDepth($root->right), $min_depth);
        }
        return $min_depth + 1;
    }
}